#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <ctime>
#include <algorithm>

#define FOR(i,a,n) for(int i=a,_n(n);i<_n;++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;

template<class T,class Cmp=less<T> >
class MergeHeap
{
    static Cmp cmp;
    struct Node
    {
        T key;
        Node* child[2];
        Node(T a = 0)
        {
            key = a;
            child[0] = child[1] = NULL;
        }
    };
    Node* root;
    Node *node,*np;
    Node* NewNode(T t)
    {
        return new (np++)Node(t);
    }
    void Push(const T t,Node*& nt)
    {
        if(!nt) nt = NewNode(t);
        else if(cmp(nt->key,t))
        {
            if(!nt->child[0]) Push(t,nt->child[0]);
            else if(!nt->child[1]) Push(t,nt->child[1]);
            else Push(t,nt->child[rand()&1]);
        }
        else
        {
            Node* np = nt;
            nt = NewNode(t);
            nt->child[0] = np;
            np = nt;
            while(np->child[0]&&np->child[0]->child[1])
            {
                np->child[1] = np->child[0]->child[1];
                np->child[0]->child[1] = NULL;
                np = np->child[0];
            }
        }
    }
    Node* Merge(Node*& np1,Node*& np2)
    {
        if(!np1) return np2;
        if(!np2) return np1;
        int cp = rand()&1;
        if(cmp(np1->key,np2->key))
        {
            np1->child[cp] = Merge(np1->child[cp],np2);
            return np1;
        }
        else
        {
            np2->child[cp] = Merge(np2->child[cp],np1);
            return np2;
        }
    }
    public:
    MergeHeap()
    {
        root = NULL;
        node = new Node[1000000];
        np = node;
    }
    void Push(T t) {Push(t,root);}
    void Pop()
    {
        if(root) root = Merge(root->child[0],root->child[1]);
    }
    T Top()
    {
        return root->key;
    }
};
int main()
{
    int T = 1000000;
    priority_queue<int> q;
    MergeHeap<int> hp;
   // REP(i,T) hp.Push(rand());
    REP(i,T) q.push(rand());
    REP(i,T)
    {
        //printf("%d ",hp.Top());
       // hp.Pop();
       //q.pop();
    }
    cout<<endl;
	return 0;
}
